#include <bits/stdc++.h>
using namespace std;

/*
1695. 删除子数组的最大得分
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

 

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]
示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104
*/

// 法一
class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        int max_sum = 0;
        int cur_sum = 0;
        int left = 0;   
        unordered_map<int, int> freq;

        for (int right = 0;right < n; right++) {
            // 增加当前元素的频率
            ++freq[nums[right]];
            cur_sum += nums[right];

            // 有重复的话就移动左指针
            while (freq[nums[right]] > 1) {
                --freq[nums[left]];     // 减少左指针的频率
                cur_sum -= nums[left];  // 从当前和中减去左指针元素
                ++left;
            }
            max_sum = max(max_sum, cur_sum);
        }
        return max_sum;
    }
};

// 法二
class Solution {
public:
// 滑动窗口逻辑 右边扩张  左边收缩 直到重复元素移除完毕
    int maximumUniqueSubarray(vector<int>& nums) {        
        bool st[10001] = {0};      // 哈希表，记录每个元素是否在当前窗口中出现过（题目限制元素范围0~10000）
        int lef = 0, rt = 0, sum = 0, res = 0;  // lef:窗口左边界，rt:窗口右边界，sum:窗口内元素和，res:最大和结果
        
        // 滑动窗口核心逻辑：右指针不断扩展窗口
        while (rt < nums.size()) {
            // 当右指针元素已存在时，收缩左边界直到重复元素被移除
            while (st[nums[rt]]) {
                st[nums[lef]] = 0;    // 标记左指针元素移出窗口
                sum -= nums[lef];      // 减去左指针元素的值
                lef++;                 // 左指针右移
            }
            // 右指针元素加入窗口
            st[nums[rt]] = 1;         // 标记当前元素已存在
            sum += nums[rt];          // 累加当前元素的值
            rt++;                     // 右指针右移
            res = max(res, sum);      // 更新最大和（窗口每扩展一次就更新一次结果）
        }
        return res;
    }
};